package leetcode;
/**
 * 1049.最后一块石头的重量Ⅱ
 * 有⼀堆⽯头，每块⽯头的重量都是正整数。
 * 每⼀回合，从中选出任意两块⽯头，然后将它们⼀起粉碎。假设⽯头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
 *
 * 如果 x == y，那么两块⽯头都会被完全粉碎；
 * 如果 x != y，那么重量为 x 的⽯头将会完全粉碎，⽽重量为 y 的⽯头新重量为 y-x。
 * 最后，最多只会剩下⼀块⽯头。返回此⽯头最⼩的可能重量。如果没有⽯头剩下，就返回 0。
 *
 * 示例：
 * 输⼊：[2,7,4,1,8,1]
 * 输出：1
 * 解释：
 * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
 * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
 * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
 * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 * 提示：
 * 1 <= stones.length <= 30
 * 1 <= stones[i] <= 1000
 *
 * 思路：
 * 本题其实就是尽量让⽯头分成重量相同的两堆，相撞之后剩下的⽯头最⼩，这样就化解成01背包问题了。
 * 是不是感觉和昨天讲解的416. 分割等和⼦集⾮常像了。
 */
public class Num_1049 {
    public static void main(String[] args) {
        System.out.println(lastStoneWeightII(new int[]{2,7})); // 5
        System.out.println(lastStoneWeightII(new int[]{2,7,3})); // 2
        System.out.println(lastStoneWeightII(new int[]{2,7,3,1})); // 1
        System.out.println(lastStoneWeightII(new int[]{2,7,4,1,8,1})); // 1
        System.out.println(lastStoneWeightII(new int[]{31,26,33,21,40})); // 5
    }
    public static int lastStoneWeightII(int[] stones) {
        //求总质量
        int sum = 0;
        for(int stone : stones){
            sum += stone;
        }
        /**
         * 分成重量相同的两堆；即使分不出来，也要分得两堆质量差最小。
         * 也就是从这一大堆石头中，挑出一小堆，其质量和<=(sum/2)尽可能接近
         */
        int n = stones.length;
        //前i个元素是否可以拼凑出j值
        boolean[][] dp = new boolean[n+1][sum/2+sum];
        //初始化
        dp[0][0] = true;
        for(int i=1; i<=n; i++){
            //前i个一定可以凑出第i个整数
            dp[i][stones[i-1]] = true;
            for(int j=1; j<=sum/2; j++){
                //看前i-1个是否能凑出j
                if(dp[i-1][j]){
                    //一定可以凑出j
                    dp[i][j] = true;
                    //还可以凑出(j+第i个整数)
                    dp[i][j+stones[i-1]] = true;
                }
            }
        }
        //找出最接近于(sum/2)的石头堆质量
        int middleSum = 0;
        for(int j=sum/2; j>0; j--){
            if(dp[n][j]){
                middleSum = j;
                break;
            }
        }
        return (sum-middleSum)-middleSum;
    }

    /** 复习 **/
    public int lastStoneWeightII2(int[] stones) {
        //最简单的情况
        if(stones.length == 1){
            return stones[0];
        }
        //先累加总和
        int sum = 0;
        for(int i : stones){
            sum += i;
        }
        // 5 2 5
        //凑出接近于(sum/2)的值，<=(sum/2)
        int bag = sum / 2;
        //dp[i][j]表示前i个整数能否凑出j
        boolean[][] dp = new boolean[stones.length + 1][bag + 1];
        //先遍历元素
        for(int i = 1; i <= stones.length; i++){
            //再遍历背包容量
            for(int j = 1; j <= bag; j++){
                //先看除了第i个元素，前面的那些元素能否凑出j
                if(dp[i-1][j]){
                    dp[i][j] = true;
                    continue;
                }
                //再看第i个元素和j的大小关系
                if(stones[i - 1] > j){
                    dp[i][j] = dp[i - 1][j];
                }else if(stones[i - 1] == j){
                    dp[i][j] = true;
                }else {
                    //选了第i个元素的情况
                    dp[i][j] = dp[i - 1][j - stones[i - 1]];
                }
            }
        }
        //此时倒着看，整个数组能凑出最接近(sum/2)的数是多少
        int ret = 0;
        for(int j = bag; j > 0; j--){
            if(dp[stones.length][j]){
                ret = j;
                break;
            }
        }
        //返回两个石头堆的差
        return (sum - ret) - ret;
    }
}
